package com.study;

import java.util.Arrays;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-10-31 16:15
 * @version: 1.0
 * @description: 统计n以内数据的个数
 **/
public class SuShu {

	/* 埃筛法：埃拉托斯特尼筛法
	要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
	   时间复制度： n * ln n
	*/
	private static int sushu(int n) {
		boolean[] isPrime = new boolean[n];
		int count = 0;
		Arrays.fill(isPrime,true); // 默认 n 以内的数都是素数
		for (int i = 2; i < n; i++) {
			if (isPrime[i]){
				for (int j = i * i; j < n ; j+=i) {
					isPrime[j] = false;
				}
				count ++;
			}
		}
		return count;
	}

	private static int sushu1(int n){
		boolean[] isPrime = new boolean[n];
		int count = 0;
		Arrays.fill(isPrime,true);
		for (int i = 2;i <= n ; i++){
			if (isPrime[i]){
				count++;
				for (int j = i*i; j < n; j += i) {
					isPrime[j] = false;
				}
			}
		}
		return count;
	}


	public static void main(String[] args) {
		System.out.println(bf(100));
		System.out.println("----------------------");
		System.out.println(sushu(100));
	}

	//----------------暴力算法 brute force---------------------------------------
	private static int bf(int n) {
		int count = 0;
		for (int i = 2; i <= n; i++) {
			if(isPrime(i)){
				count++;
			}

		}
		return count;
	}

	// 因为2*6 = 12、6 * 2 = 12 所以暴力算法也不用全部遍历，只要遍历一半就可以了
	// i * i < n 此判断条件有问题，会多 4,9,25,49 必须是 <=   时间复杂度为 n * sqrt(x)
	private static boolean isPrime(int n) {
		for (int i = 2; i * i <= n; i++) {
			if (n % i == 0){
				return false;
			}
		}
		return true;
	}

}
